'''
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
'''

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        return self.built(nums,0,len(nums)-1)

    def built(self,nums,start,end):
        if start > end:
            return None
        
        index,maxvalue = -1,-sys.maxsize
        for i in range(start,end+1):
            if nums[i] > maxvalue:
                maxvalue = nums[i]
                index = i
        
        root = TreeNode(maxvalue)
        root.left = self.built(nums,start,index-1)
        root.right = self.built(nums,index+1,end)